/**
 * 给定数组A，不能取相邻元素，问能够取到的最大和是多少
 * 令Xi是到i为止取i的最大和，Yi是到i为止不取i的最大和
 * Di是i以内的最大和
 * 则 Xi = D[i-2] + Ai
 *    Yi = D[i - 1]
 *    Di = max(Xi, Yi)
 * 
 * 手动初始化前2个即可
 */
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(1 == n) return nums[0];
        if(2 == n) return max(nums[0], nums[1]);

        vector<int> X(n, 0), Y(n, 0), D(n, 0);
        X[0] = nums[0];
        Y[0] = 0;
        D[0] = X[0];

        X[1] = nums[1];
        Y[1] = nums[0];
        D[1] = max(X[1], Y[1]);

        for(int i=2;i<n;++i){
            X[i] = D[i - 2] + nums[i];
            Y[i] = X[i - 1];
            D[i] = max(X[i], Y[i]);
        }
        
        return D[n - 1];
    }
};